Сапёр 9x9

Игра Сапёр на поле 9 на 9.

Задача

Как обычно, открыть все ячейки, стараясь не открыть ячейки с минами.

Общее описание

Квадратное поле 9 x 9 (1…9 x 1…9). Количество мин задаётся при начале игры. Что считать координатой X, а что Y, решайте сами, главное, чтобы быть в этом последовательными. Как и в начальных версиях игры под Windows мины расставляются до первого хода. Поэтому подорваться можно уже первым ходом. Всё поле, чтобы не держать в памяти как ПМК 😊, проще рисовать на бумаге. ПМК только выдаёт количество мин вокруг указанной ячейки после каждого хода.

Игровой процесс

Начало

Перед первым запуском несколько констант в регистры. Если используете загрузку образа в эмулятор, то они уже введены.

Регистр Значение
R6 Случайное число. Можно оставить нулевым.
R7 73
R9 0.11828112
Ra 0.35000025
Rс 86
Rd 63

Начало игры: вводим количество мин от 1 до 63. Рекомендую 20. И В/О С/П.

ПМК расставит на поле мины случайным образом и по окончании выдаст 3.5000025-01.

Игра

Вы задаёте координаты ячейки, которую хотите проверить, в виде двузначного числа. От 11 до 99 (без нулей!). Как указано выше, сами выбирайте, какой разряд считать координатой по горизонтали, какой по вертикали. И после С/П ПМК отобразит на экране количество мин вокруг указанной ячейки. Либо ЕГГ0Г , если подорвались, т. е. в указанном месте и была мина.

Окончание

Если вы нашли все мины, или подорвались, или просто не нравится текущая расстановка, то начало новой игры как указано выше, только никаких вводов значений в регистры не потребуется. В связи с тем, что генератор случайных чисел постоянно меняет базовое значение, в новой игре будет другая расстановка.

Контроль со стороны ПМК

Программа достаточно медленная, поэтому если используете эмулятор ПМК с ускорением, то включите ускорение. Приятной игры!

Далее только для тех, кто не только играет…

Идеи реализации

В отличие от пользователя, ПМК использует поле не 9 x 9, а 11 x 11. Получаются координаты от 00 до 110, где последняя цифра (для определённости) – это номер по горизонтали.

Лучше показать поле в виде таблицы с числовыми координатами:

100101102103104105106107108109110
90919293949596979899100
8081828384858687888990
7071727374757677787980
6061626364656667686970
5051525354555657585960
4041424344454647484950
3031323334353637383940
2021222324252627282930
1011121314151617181920
0001020304050607080910

В данном случае серая зона по краям – это виртуальные координаты, которые знает ПМК, но не видит пользователь. Обратите внимание, что самый правый ряд – это копия самого левого. При линейном представлении справа от 19 идёт 20, но слева от 21 тоже 20.

ПМК для распределения мин использует только внутреннее поле, но хранит и в расчётах использует всю таблицу. Это позволяет держать границы поля свободными от мин, что упрощает функции подсчёта.

Что касается обхода, то это лучше увидеть на центральном голубом квадрате. Для примера, пусть пользователь указал координаты 55. В этом случае нужно посчитать мины в ячейках квадрата вокруг него, т. е. в координатах 44, 45, 46, 54, 56, 64, 65, 66.

В общем случае, для любой ячейки с координатами P, квадрат обхода – это ячейки с координатами P − 11, P − 10, P − 9, P − 1, P + 1, P + 9, P + 10, P + 11. Вот для чего введены виртуальные границы. Чтобы на краях не заниматься сложными расчётами, потому что в виртуальных ячейках всегда нет мин.

Теперь технические детали. У ПМК нет столько регистров памяти, чтобы хранить 111 чисел. Поэтому он для каждой ячейки использует один бит. Для операций с битами используются шестнадцатеричные представления чисел. Т. к. одна шестнадцатеричная цифра может представлять 4 бита, то 7 цифр (максимум в шестнадцатеричных операциях) 7 × 4 = 28. Итого получается 4 × 28 = 112. Как раз хватит для нашего случая.

Второй момент, это вычисление координат обхода. Для удобства, формула выше для вычисления ячеек обхода с произвольной координаты P, хранится в относительном виде. К начальному P − 11 потом добавляется: +1, +1, +8, +2, +8, +1, +1. А это как раз составляет содержимое загадочной константа из R8 (0.11828112). В ней последняя цифра может быть произвольной при расчётах, потому что используется только как флаг окончания обхода. Но задана явно как два, чтобы использовать эту же константу для косвенного перехода на адрес 12.

Текст программы

 # |  00 01 02 03 04 05 06 07 08 09
 00 |  К[x] x→П0 FLg П→xd П→x0 − F√ 0 x→П1 x→П2
 10 |  x→П4 x→П8 КППc ВП 1 КППc + КПП7 Кx=09 +
 20 |  КП→xe К∨ Кx→Пe FL0 12 П→xa С/П К[x] Кx≠0a Кx≥0a
 30 |  x→П0 ВП Кx≠0a FLg К[x] Кx=0a П→x9 x→П3 П→x0 КПП7
 40 |  Кx=07 x→П5 1 1 − П→x0 + x→П0 КПП7 Fx≠0
 50 |  52 КП→x5 П→x3 ВП 1 В↑ К{x} x→П3 Fx=0 44
 60 |  П→x5 БП 26 4 ÷ К[x] FВx К{x} П→xa ÷
 70 |  Fex К[x] В/О КППd x→Пe <-> КППd <-> 1 +
 80 |  F10x + КП→xe К∧ К{x} В/О П→x6 7 × Fπ
 90 |  + К{x} x→П6 КНОП ВП В/О

Распределение регистров

R0 Рабочий регистр.
R1, R2, R4, R8 Поле мин в битовом представлении.
R3 Рабочий регистр. Используется для вычисления следующего смещения при обходе вокруг.
R5 Рабочий регистр. Счётчик количества мин вокруг заданной ячейки.
R6 Случайное число.
R7 73. Адрес процедуры проверки наличия в указанной ячейке мины.
R9 1.1828112^-01. Константа для вычисления координат ячеек вокруг заданной, а также адрес перехода 12.
Ra 3.1000025^-01. Константа для вычисления 2x, а также адрес перехода 25.
Rb Не используется
Rc 86. Адрес процедуры генерации случайной цифры.
Rd 63. Адрес процедуры деления на 4.
Re Рабочий регистр. Содержит номер регистра – поля, в котором идёт проверка наличия мин (1, 2, 4, 8).

Объяснение работы программы

Поняв основные идеи, перейдём к программе. Сначала рассмотрим вспомогательные процедуры.

  1. Процедура деление на 4 с остатком. Причем остаток сразу используется как показатель функции 2x. Она начинается с адреса 63 (регистр Rd). Для числа X процедура возвращяет пару (в X и Y): 2(X mod 4), X div 4. Сначала просто находит целую часть от деления. А второе число получается чуть сложнее. Для этого используется хитрая константа из Ra (0.35000025). Она примерно равна обратной величине от 4 × Ln(2), только подобрана так, чтобы после вычисления можно было сразу взять целую часть, а не как для встроенной функции Fxy, которая для 23 даёт 7.9999993. К тому же Fex вычисляется быстрее. Получается e(X mod 4) × 4 × Ln(2), что даёт 2X, или числа 1, 2, 4, 8. Хвостик хитрой константы используется как адрес перехода 25. А обратная величина используется вместо прямой именно для возможности косвенной адресации по хвосту.
  2. Процедура проверки наличия в указанной ячейке мины. Или преобразование целого числа [0…110] из регистра X в номер регистра (в Re) для определения поля для тестирования, бита для проверки в RY, и сам результат проверки битовой операции (не ноль, если есть).
    Подпрограмма начинается с адреса 73 (R7). Сначала число делиться на 4 (через процедуру 1). Затем число из множества [1, 2, 4, 8] используется как номер регистра. А целая часть [0…27] снова делиться на 4. Целая часть используется для определения разряда (10 в степени [0…6] + 1), а число [1, 2, 4, 8] складывается с номером разряда и получается бит для тестирования, что и делается с помощью операции К∧. Кстати, сам бит остаётся в RY, что позволит его же использовать для установки бита.
    Возвращается или ноль – нет мин, или не ноль (причём меньше единицы) – есть мина.
  3. Процедура генератора случайной цифры. Начинается с адреса 86 (Rc). Формула последовательности для генерации случайного числа N = {7 × N + π}. Хвост процедуры использует недокументированные возможности оператора ВП для восстановления 7, с заменой её на первую цифру случайного числа.

Теперь можно рассмотреть всю программу.

Адреса 00..06. Ввод числа мин с проверкой. Сохраняется счётчик количества мин и делается его проверка на ⩾ 1 через FLg, и на ⩽ 63, используя разницу с Rd и F√.

Адреса 07..11. Обнуление битовых полей для хранения положения мин.

Адреса 12..24. Расстановка мин. Дважды используется процедура генерации (Rc) случайной цифры 1..9 для получения двузначного числа координаты без нулей. Через процедуру проверки (R7) проверяется, что мина не ставится повторно. И если её там нет, то используя факт, что маска бита остался в RY (а Re содержит номер поля для бита), полученный при проверке ноль убирается с помощью + и результат К∨ сохраняется. Цикл повторяется по количеству мин.

Адреса 25..26. Вывод флага окончания инициализации или неудачного выбора координаты для проверки и остановка для ожидания хода пользователя. Адрес этого кода хранится в Ra.

Адреса 27..35. Проверка ввода пользователя. После простой проверки на > 0 и сохранения в R0, с помощью недокументированной возможности удаляется первая значащая (не ноль) цифра, чтобы проверить, что число содержит более одной цифры. А затем, что не более двух, т. к. Lg(9) меньше единицы и целая часть нулевая. Для бо́льших чисел это не так.

Адреса 36..41. Инициализация цикла обхода и проверка мины в ячейке. Константа для обхода из R9 сохраняется в R3. Делается проверка хода пользователя (R0) процедурой из R7. Если результат удачный (ноль), то этот ноль инициализирует счётчик числа мин вокруг.
Стоит пояснить случай не ноль – нарвались на мину. В этом случае число будет меньше единицы, и переход на процедуру проверки (R7) заставит её проверить фактически ячейку 0. А ячейка с номером ноль всегда без мины. Но возврат из процедуры будет уже на адрес 01, как результат В/О без ПП. А там FLg от нуля и выдаст ошибку.

Адреса 42..59. Цикл обхода с подсчётом количества мин. Начинается с −11 (почему обычный минус от нуля справа, а не /-/, будет ясно чуть позже), которое прибавляется к координатам выбранной ячейки. Затем делается проверка через процедуру в R7, и если мина найдена, то увеличение счётчика в R5. Затем идёт вычисление прибавки, которое записано в первом разряде регистра R3. После умножения на 10 и сдвига, берётся дробная часть (первый разряд отсекается), сохраняется. И если больше не осталось, то цикл завершается. А если что-то есть, то целое с дробной частью удачно переходит на минус по адресу 44, тем самым оставляя только этот первый разряд, который снова прибавляется к координатам и т. д.

Адреса 60..62. Вывод итога для пользователя. Просто вывод значения счётчика и переход на остановку.

Оставшаяся часть программы уже рассмотрена ранее, когда разбирались подпрограммы.